package lanqiao._02算法训练.page01;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？
 * 输入格式
 * 　　一行四个数字a,b,c,d。
 * 输出格式
 * 　　如果跳不到，输出-1；否则输出最少跳到的步数。
 * 样例输入
 * 1 1 2 3
 * 样例输出
 * 1
 * 数据规模和约定
 * 　　0<a,b,c,d≤8且都是整数。
 * 思路：
 * 广度优先搜索
 * 深度优先搜索
 * @since 2022 - 10 - 29 - 21:58
 */
public class _06跳马 {
}
class Main6{
    static int a, b, c, d;
    static int[][] dirs = {
            {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
            {1, -2}	, {2, -1}, {2, 1}, {1, 2}
    };
    static int min = Integer.MAX_VALUE;
    static boolean[][] vis;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        vis = new boolean[8][8];
        dfs(a, b, 0);
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
//        int cnt = bfs(a, b);
//        System.out.println(cnt);
    }
    //深度优先搜索
    static void dfs(int x, int y, int cnt){
        if(x == c && y == d){
            min = Math.min(min, cnt);
            return;
        }
        //多余8次剪枝
        if(cnt > 8) return;
        vis[x - 1][y - 1] = true;
        for(int[] dir : dirs){
            int nx = x + dir[0], ny = y + dir[1];
            if(nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8 && !vis[nx - 1][ny - 1]){
                dfs(nx, ny, cnt + 1);
            }
        }
        vis[x - 1][y - 1] = false;
    }
    //广度优先搜索
    static int bfs(int a, int b){
        if(a == c && b == d) return 0;
        int cnt = 1;
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{a, b});
        vis[a - 1][b - 1] = true;
        int[] point;
        int x, y;
        //当前层节点数、下一层节点数
        int curCnt = 1, nextCnt = 0;
        while(!queue.isEmpty()){
            point = queue.poll();
            //当前层减1
            curCnt--;
            //八个方位
            for(int[] dir : dirs){
                x = point[0] + dir[0];
                y = point[1] + dir[1];
                if(x == c && y == d) return cnt;

                if(x >= 1 && x <= 8 && y >= 1 && y <= 8 && !vis[x - 1][y - 1]){
                    vis[x - 1][y - 1] = true;
                    queue.offer(new int[]{x, y});
                    nextCnt++;
                }
            }
            //下一层
            if(curCnt == 0){
                curCnt = nextCnt;
                nextCnt = 0;
                //层数加1
                cnt++;
            }
        }
        return -1;
    }
}

